package mergesort

// 两半都已经排序好了，有顺序来
func MergeSort01(arr []int) (res []int) {
	mid := len(arr) >> 1
	var left int = 0
	var right int = mid + 1
	for left <= mid && right < len(arr) {
		if arr[left] <= arr[right] {
			res = append(res, arr[left])
			left++
		} else {
			res = append(res, arr[right])
			right++
		}
	}
	for left <= mid {
		res = append(res, arr[left])
		left++
	}
	for right < len(arr) {
		res = append(res, arr[right])
		right++
	}
	return
}

// 总是不对
func MergeSort02(arr []int) []int {
	if len(arr) < 2 {
		return arr
	}
	mid := len(arr) / 2
	left := MergeSort02(arr[0:mid])
	right := MergeSort02(arr[mid:])

	return subMergeSort(left, right)

}

func subMergeSort(left, right []int) []int {
	var i ,j int = 0,0
	var res []int
	for i<len(left) && j<len(right) {
		if left[i] < right[j]{
			res = append(res, left[i])
			i++
		}else{
			res = append(res, right[j])
			j++
		}
	}
	for i<len(left) {
		res = append(res, left[i])
		i++
	}
	for j<len(right) {
		res = append(res, right[j])
		j++
	}
	return res
}

// func MergeSort02(arr []int, left,right int ){
// 	if left == right{
// 		return
// 	}
// 	mid := left + (right-left)/2
// 	MergeSort02(arr,left,mid)
// 	MergeSort02(arr,mid+1,right)
// 	subMerge(arr,left ,mid+1, right)
// 	fmt.Println(arr)
// }

// func subMerge(arr []int, left,right,rightBound int){
// 	mid := right-1
// 	i := left
// 	j := right
// 	var tmp []int
// 	for i<=mid&&j<=rightBound{
// 		if arr[i] <= arr[j]{
// 			tmp = append(tmp, arr[i])
// 			i++
// 		}else{
// 			tmp = append(tmp, arr[j])
// 			j++
// 		}
// 	}
// 	for i<=mid{
// 		tmp = append(tmp, arr[i])
// 	}
// 	for j <= rightBound{
// 		tmp = append(tmp, arr[j])
// 	}
// 	arr = append(arr, tmp...)

// }
